import java.util.*;

/**
 * @Author 12138
 * @Description：
 */
public class Test {


    public static List<String> topKFrequent(String[] words, int k) {
        //1、每个单词出现的次数
        Map<String,Integer> map = new HashMap<>();
        for(String s : words) {
            if(map.get(s) == null) {
                map.put(s,1);
            }else {
                //以前有
                int val = map.get(s);
                map.put(s,val+1);
            }
        }

        //2、已经统计完毕，创建小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());//根据字母顺序 变成大根堆
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        //3、下一步要做的就是 遍历MAP了
        for(Map.Entry<String,Integer> entry : map.entrySet()) {
            if(minHeap.size() < k) {
                minHeap.offer(entry);
            }else {
                Map.Entry<String,Integer> top = minHeap.peek();
                if(top.getValue().compareTo(entry.getValue()) == 0) {
                    //频率一样的情况下，判断key值，key小的入
                    if(top.getKey().compareTo(entry.getKey()) > 0) {
                        //出 top 入entry
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else {
                    if(top.getValue().compareTo(entry.getValue()) < 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        //4、接下来 要把小根堆里面的元素 出出来 放到 一个集合里面，然后逆置
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String s = minHeap.poll().getKey();
            ret.add(s);
        }
        Collections.reverse(ret);
        return ret;
    }


    public static void main(String[] args) {
        String[] strings = {"a","b","c","c"};
        List<String> ret = topKFrequent(strings,3);
        System.out.println(ret);
    }











    /**
     * 统计每个数据出现的次数
     * K-V
     *
     * @param array
     */
    public static void func2(int[] array) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            //以前没有
            if(map.get(array[i]) == null) {
                map.put(array[i],1);
            }else {
                //以前有
                int val = map.get(array[i]);
                map.put(array[i],val+1);
            }
        }

        System.out.println(map);
    }

    public static void main2(String[] args) {
        int[] array = {1,2,3,2,1,2,1};
        func2(array);
    }


    /*
    TODO: 如果不使用Map，直接用链表的知识 怎么做？
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        while(cur != null) {
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }

        //第一遍变量完成，此时需要遍历第2遍 来修改next和random的值

        cur = head;
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }

        return map.get(head);
    }*/

    /**
     * 去重
     * @param array
     */
    public static void func1(int[] array) {
        Set<Integer> set = new TreeSet<>();
        for (int i = 0; i < array.length; i++) {
            set.add(array[i]);
        }
        System.out.println(set);
    }

    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
           if(!set.contains(nums[i])) {
               set.add(nums[i]);
           }else {
               set.remove(nums[i]);
           }
        }
        //这里走完之后 set当中 只要一个元素
        for (int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }

    public int numJewelsInStones(String jewels, String stones) {

        int count = 0;
        Set<Character> set = new HashSet<>();

        for(char c : jewels.toCharArray()) {
            set.add(c);
        }

        for(char c : stones.toCharArray()) {
            if(set.contains(c)) {
                count++;
            }
        }

        return count;
    }





    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str1 = in.nextLine();
            String str2 = in.nextLine();
            func(str1,str2);
        }
    }

    /**
     * @param str1 应该输入的
     * @param str2 实际输入的
     */
    public static void func(String str1,String str2) {
        Set<Character> set = new HashSet<>();
        //把实际输入的放到集合当中
        for (char ch : str2.toUpperCase().toCharArray()) {
            set.add(ch);
        }
        Set<Character> setBroken = new HashSet<>();
        for (char ch : str1.toUpperCase().toCharArray()) {
            if(!set.contains(ch) && !setBroken.contains(ch)) {
                setBroken.add(ch);//把坏了的键 放到单独的集合
                System.out.print(ch);
            }
        }
    }

}